package Array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.concurrent.Executor;

/****
 * 给出一个元素无序的数组，求出使得其左边的数都小于等于它，右边的数都大于等于它的所有数字。
 *
 * 举例：
 *
 * （1）1,2,3,1,2,0,5,6 ： 输出5,6
 *
 * （2）1,2,3,1,2,0,5,5 ： 输出5（第一个5）
 *
 * （3）1,2,3,4,5,6,7 ： 输出1,2,3,4,5,6,7

 *
 *
 * */
class GetNumber {

    public ArrayList<Integer> getNumber(int[] nums){
        ArrayList<Integer> res = new ArrayList<>();
        //求得其左边的数都小于它，右边的数都大于等于它的所有数字
        //从左向右遍历，每个位置都记录到当前位置的最小值。
        int len = nums.length;
        int[] min = new int[len];
        min[0] = nums[0];
        for (int i = 1; i < len; i++) {
            min[i] = Math.min(nums[i], min[i-1]);
        }
        System.out.println(Arrays.toString(min));
        //从右向左遍历，每个位置都记录到当前位置的最大值
        int[] max = new int[len];
        max[len-1] = nums[len-1];
        for (int i = len-2; i >=0 ; i--) {
            max[i] = Math.max(nums[i], max[i+1]);
        }
        System.out.println(Arrays.toString(max));
        for (int i = 0; i < len; i++) {

            if(i==len-1 && nums[i] >= nums[i-1]){
                res.add(nums[i]);
                continue;
            }
            //当前值大于等于左边的，小于等于右边的
            if(nums[i] >= max[i-1] && nums[i] <= min[i+1]){
                res.add(nums[i]);
            }
        }

        return res;
    }

    public static void main(String[] args) {
        GetNumber g = new GetNumber();
        System.out.println(g.getNumber(new int[]{1,2,3,1,2,0,5,6}));
//        System.out.println(g.getNumber(new int[]{1,2,3,1,2,0,5,5}));
//        System.out.println(g.getNumber(new int[]{1,2,3,4,5,6,7}));
    }
}
